#! /usr/bin/env python
#
"""Classes for computing graph homology.
"""
__docformat__ = 'reStructuredText'


## logging subsystem

import itertools
import logging


## application-local imports

from combinatorics import (
    bernoulli,
    factorial,
    sign_exp,
    )
from homology import *
from rg import MgnNumberedGraphsIterator, NumberedFatgraph
from rational import Rational
from valences import vertex_valences_for_given_g_and_n


def FatgraphComplex(g, n):
    """Return the fatgraph complex for given genus `g` and number of
    boundary components `n`.

    This is a factory method returning a `homology.ChainComplex`
    instance, populated with the correct vector spaces and
    differentials to compute the graph homology of the space
    `M_{g,n}`.
    """
    logging.info("Stage I: Computing fat graphs complex for g=%d, n=%d ...", g, n)

    ## Minimum number of edges is attained when there's only one
    ## vertex; so, by Euler's formula `V - E + n = 2 - 2*g`, we get:
    ## `E = 2*g + n - 1`.
    min_edges = 2*g + n - 1
    logging.debug("  Minimum number of edges: %d", min_edges)
    
    ## Maximum number of edges is reached in graphs with all vertices
    ## tri-valent, so, combining Euler's formula with `3*V = 2*E`, we
    ## get: `E = 6*g + 3*n - 6`.  These are also graphs corresponding
    ## to top-dimensional cells.
    top_dimension = 6*g + 3*n - 6
    logging.debug("  Maximum number of edges: %d", top_dimension)

    #: list of primitive graphs, graded by number of edges
    generators = [ NumberedFatgraphsList() for dummy in xrange(top_dimension) ]

    # gather graphs
    chi = Rational(0)
    for graph in MgnNumberedGraphsIterator(g,n):
        grade = graph.num_edges - 1
        # compute orbifold Euler characteristics (needs to include *all* graphs)
        chi += Rational(sign_exp(grade-min_edges), graph.num_automorphisms())
        # discard non-orientable graphs
        if not graph.is_oriented():
            continue
        generators[grade].append(graph, key=graph.underlying)

    # build chain complex
    C = ChainComplex(top_dimension)
    for i in xrange(top_dimension):
        # set support module and differential
        C[i] = (FatgraphComplexSlice(generators[i]),
                graph_homology_differential)
        logging.debug("  Initialized grade %d chain module (with dimension %d)",
                     i, len(generators[i]))
    C.orbifold_euler_characteristics = chi
    return C


def graph_homology_differential(graph):
    """The graph homology differential (the same for every grade).

    Return a linear combination (with alternating signs) of
    contractions of all non-loop edges of the given graph.
    """
    result = []
    for l in xrange(graph.num_edges):
        if not graph.is_loop(l):
            dg = graph.contract(l)
            if dg.is_oriented():
                result.append((dg, sign_exp(graph.edge_numbering[l])))
    return result
        

class FatgraphComplexSlice(VectorSpace):
    """Return vector space generated by a given set of fatgraphs.

    This is different from the base `VectorSpace` class in that the
    `coordinates` method will detect different presentations of the
    same fatgraph.
    """
    
    if __debug__:
        def __init__(self, base):
            for (i, graph) in enumerate(base):
                assert graph.numbering is not None, \
                       "FatgraphComplexSlice.__init__:"\
                       " initialized with non-numbered graph `%s`" \
                       " (at position %d)" \
                       % (graph, i)
            VectorSpace.__init__(self, base)
                
    def coordinates(self, combo):
        """Return (sparse) coordinate vector of linear combination `combo`.
        See `VectorSpace.coordinates()` for details.
        """
        # canonicalize graphs
        for x in xrange(len(combo)):
            graph = combo[x][0]

            # try to determine which element in base `graph`
            # is isomorphic to.
            try:
                canonical = self.base[self.base.index(graph)]
                assert canonical == graph and graph == canonical
            except ValueError:
                raise ValueError, \
                      "Cannot find canonical representative for graph `%s`." \
                      % (repr(graph),)

            # alter the `combo` list in-place
            combo[x] = (canonical, combo[x][1] * graph.projection(canonical))

        # call method from superclass
        return VectorSpace.coordinates(self, combo)



class NumberedFatgraphsList(object):
    """A specialized `list` clone, with O(N^(1/2))-time comparisons.
    """

    def __init__(self):
        self.__keys = []
        self.__lens = []
        self.__lists = []

    def __iter__(self):
        return itertools.chain(* self.__lists)

    def __contains__(self, value):
        try:
            self.index(value)
            return True
        except ValueError:
            return False

    def __delitem__(self, i):
        for n, l in enumerate(self.__lists):
            L = self.__lens[n]
            if i < L:
                del l[i]
                self.__lens[n] -= 1
            else:
                i -= L
        raise IndexError, "list index out of range"

    def __getitem__(self, i):
        for l, L in itertools.izip(self.__lists, self.__lens):
            if i < L:
                return l[i]
            else:
                i -= L
        raise IndexError, "list index out of range"

    def __len__(self):
        return sum(self.__lens)

    def __setitem__(self, i, item):
        for l, L in itertools.izip(self.__lists, self.__lens):
            if i < L:
                l[i] = item
            else:
                i -= L
        raise IndexError, "list index out of range"

    def append(self, item, key):
        try:
            i = self.__keys.index(key)
            self.__lists[i].append(item)
            self.__lens[i] += 1
        except ValueError:
            self.__keys.append(key)
            self.__lists.append([item])
            self.__lens.append(1)

    def expand(self, lst, key):
        try:
            i = self.__keys.index(key)
            self.__lists[i].expand(lst)
            self.__lens[i] += len(lst)
        except ValueError:
            self.__keys.append(key)
            self.__lists.append(lst)
            self.__lens.append(len(lst))

    def index(self, value):
        # XXX: this is the only non-generic code here
        assert isinstance(value, NumberedFatgraph), \
               "NumberedFatgraphList.index: "\
               " looking up non-NumberedFatgraph instance `%s`" \
               % value
        key = value.underlying

        # how many items are in lists preceding the one containing key?
        i = self.__keys.index(key)
        return self.__lists[i].index(value) + sum(self.__lens[0:i])
        


## main: run tests

if "__main__" == __name__:
    import doctest
    doctest.testmod(optionflags=doctest.NORMALIZE_WHITESPACE)
